/*
 * Copyright (c) 2012 Craig Weinhold (cweinhold@gmail.com)
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <stdint.h>
#include <unistd.h>
#include <errno.h>
#include <fcntl.h>
#include <stdlib.h>
#include <signal.h>
#include <syslog.h>
#include <string.h>
#include <stdio.h>
#include <time.h>
#include <poll.h>

#include "sequence.h"

static int source_compare(struct source_state *a, struct source_state *b)
{
	if (a->sourceinfo.version < b->sourceinfo.version) return -1;
	if (a->sourceinfo.version > b->sourceinfo.version) return 1;
	if (a->sourceinfo.xs.source_id == b->sourceinfo.xs.source_id) return 0;
	return (a->sourceinfo.xs.source_id > b->sourceinfo.xs.source_id ? 1 : -1);
}

SPLAY_PROTOTYPE(source_tree, source_state, tp, source_compare);
SPLAY_GENERATE(source_tree, source_state, tp, source_compare);

struct source_state *find_source(struct seqinfo *seq, struct sourceinfo *si)
{
	struct source_state tmp, *source;

	bzero(&tmp, sizeof(tmp));
	memcpy(&tmp.sourceinfo, si, sizeof(tmp.sourceinfo));
	source = SPLAY_FIND(source_tree, &seq->source_tree, &tmp);
	return (source);
}

struct source_state *new_source(struct seqinfo *seq, struct sourceinfo *si)
{
	struct source_state *source;

	seq->num_sources++;
	if (seq->num_sources > MAX_SOURCES) {
		source = TAILQ_LAST(&seq->source_list, source_list);
		TAILQ_REMOVE(&seq->source_list, source, lp);
		SPLAY_REMOVE(source_tree, &seq->source_tree, source);
		free(source);
		seq->num_sources--;
	}

	if ((source = calloc(1, sizeof(*source))) == NULL)
		logerrx("%s: calloc failed", __func__);

	memcpy(&source->sourceinfo, si, sizeof(source->sourceinfo));
	source->window = (si->version == 9)  ? SEQUENCE_WINDOW_V9 : SEQUENCE_WINDOW_V5;

	logit(LOG_DEBUG, "new source version %u window %u", si->version, source->window);

	TAILQ_INSERT_HEAD(&seq->source_list, source, lp);
	SPLAY_INSERT(source_tree, &seq->source_tree, source);
	return (source);
}

void sequence_v5(struct peer_state *peer, uint32_t sequence, u_int nflows, uint8_t engine_type, uint8_t engine_id)
{
	struct sourceinfo tmp;

	bzero(&tmp, sizeof(tmp));
	tmp.version = 5;
	tmp.xs.engine_info.engine_type = engine_type;
	tmp.xs.engine_info.engine_id = engine_id;

	sequence_update(peer, sequence, nflows, 1, nflows, &tmp);
}

void sequence_v7(struct peer_state *peer, uint32_t sequence, u_int nflows)
{
	struct sourceinfo tmp;

	bzero(&tmp, sizeof(tmp));
	tmp.version = 7;

	sequence_update(peer, sequence, nflows, 1, nflows, &tmp);
}

void sequence_v9(struct peer_state *peer, uint32_t sequence, uint32_t source_id, uint32_t nflows)
{
	struct sourceinfo tmp;

	bzero(&tmp, sizeof(tmp));
	tmp.version = 9;
	tmp.xs.source_id = source_id;

	sequence_update(peer, sequence, 1, 1, nflows, &tmp);
}

void sequence_update(struct peer_state *peer, uint32_t sequence, u_int length,
		uint32_t num_packets, uint32_t num_flows,
		struct sourceinfo *si)
{
	struct source_state *st;
	uint32_t next = sequence + length;
	struct seqinfo *seq = peer->seq;
	int ok = 0;
	int lost = 0;
	int reset = 0;
	int dup = 0;
	int i, j;
	int bigwindow;

	if (seq == NULL) {		/* source struct not initialized */
		if ((seq = calloc(1, sizeof(*seq))) == NULL)
			logerrx("%s: calloc failed", __func__);
		peer->seq = seq;
	}

	st = find_source(seq, si);
	if (st == NULL) {
		st = new_source(seq, si);
	}
	else {
		/* Push source to front of LRU queue */
		if (st != TAILQ_FIRST(&seq->source_list)) {
			TAILQ_REMOVE(&seq->source_list, st, lp);
			TAILQ_INSERT_HEAD(&seq->source_list, st, lp);
		}
	}

	if (st->entries) {				// important that all math be wrap-safe
		bigwindow = st->window << 4;		// if sequence numbers are more than 16x from the actual window, then reset

		if ( (st->seqnum[0] >= bigwindow) && (sequence < st->seqnum[0] - bigwindow) ) {			// sequence is way low
			st->entries = 0;
			reset = 1;
		}
		else if ( (sequence >= bigwindow) && (sequence - bigwindow > st->seqnum[st->entries-1]) ) {	// sequence is way high
			st->entries = 0;
			reset = 1;
		}
	}

	for (i=0; i<st->entries; i++) {
		if ((sequence >= st->seqnum[i]) && (sequence < st->nextnum[i])) {	// overlap or duplicate sequence
			ok = 1;
			dup++;
			break;
		}

		else if (next == st->seqnum[i]) {					// sequence is snug before 'i'
			st->seqnum[i] = sequence;
			ok = 1;
			break;
		}
		else if (sequence == st->nextnum[i]) {					// sequence is snug after 'i'
			if (i < (st->entries - 1) ) {
				if ( next == st->seqnum[i+1] ) {			// and also snug before 'i+1'
					st->nextnum[i] = st->nextnum[i+1];
					for (j=i+1; j<st->entries-1; j++) {
						st->seqnum[j] = st->seqnum[j+1];
						st->nextnum[j] = st->nextnum[j+1];
					}
					st->entries--;
					ok = 2;
					break;
				}
			}
			st->nextnum[i] = next;
			ok = 3;
			break;
		}
		if (sequence < st->seqnum[i]) {					// sequence is somewhere before 'i'

			if (st->entries == MAX_SEQUENCE_ENTRIES) {		// but no room to store it...
				st->nwindowfail++;

				if (i == 0) {					// overwrite position 0
					ok = 4;
					break;
				}

				for (j=0; j<i-1; j++) {				// drop position 0 and squeeze this in
					st->seqnum[j] = st->seqnum[j+1];
					st->nextnum[j] = st->nextnum[j+1];
				}
				st->seqnum[i-1] = sequence;
				st->nextnum[i-1] = next;
				ok = 5;
				break;
			}

			for (j=st->entries-1; j>=i; j--) {
				st->seqnum[j+1] = st->seqnum[j];
				st->nextnum[j+1] = st->nextnum[j];
			}
			st->seqnum[i] = sequence;
			st->nextnum[i] = next;
			st->entries++;
			ok = 6;
			break;
		}
	}

	if (! ok) {								// sequence still not set; it belongs on top

		if (st->entries == MAX_SEQUENCE_ENTRIES) {			//    if no space, drop position 0 and calculate loss
			lost += st->seqnum[1] - st->nextnum[0];

			for (i=0; i<st->entries-1; i++) {
				st->seqnum[i] = st->seqnum[i+1];
				st->nextnum[i] = st->nextnum[i+1];
			}
			st->entries--;
		}

		st->seqnum[st->entries] = sequence;				// add sequence to top
		st->nextnum[st->entries] = next;
		st->entries++;
	}

	if ((st->entries > 1) && (st->seqnum[0] + st->window > st->seqnum[0])) {	// if multiple sequences and not near wrap

		if (st->nextnum[0] + st->window < st->nextnum[st->entries-1]) {		// if oldest ends outside the window,
			lost += st->seqnum[1] - st->nextnum[0];				// 	drop it and calculate loss 

			for (i=0; i<st->entries-1; i++) {
				st->seqnum[i] = st->seqnum[i+1];
				st->nextnum[i] = st->nextnum[i+1];
			}
			st->entries--;
		}
		else if (st->seqnum[0] + st->window < st->seqnum[st->entries-1]) {	// if oldest begins outside the window, but ends in the window
			st->seqnum[0] = st->seqnum[st->entries-1] - st->window;		//	update its beginning
		}
	}

	/* peer counters */
	peer->nlost += lost;
	peer->nreset += reset;
	peer->ndup += dup;

	/* source counters */
	st->nlost += lost;
	st->nreset += reset;
	st->ndup += dup;
	st->npackets += num_packets;
	st->nflows += num_flows;

/* debug code, when needed

	logit(LOG_DEBUG, "update sequence=%u length=%u, packets=%u, flows=%u, result=%d entries=%d lost=%d reset=%d",
			sequence, length, num_packets, num_flows, ok, st->entries, lost, reset);

        for (i=0; i<st->entries; i++) {
                logit(LOG_DEBUG, "%02d %08d %08d", i, st->seqnum[i], st->nextnum[i]);
        }
*/

}

void dump_sources( char *peerstr, struct peer_state *peer )
{
	struct source_state *source;
	static char buf_tmp[128];
	int i = 0;

	if (peer->seq == NULL) {
		logit(LOG_INFO, "%s has no sequence structure", peerstr);
		return;
	}

	SPLAY_FOREACH(source, source_tree, &peer->seq->source_tree) {
		i++;
		sprintf(buf_tmp, peerstr, i);

		logit(LOG_INFO, "%s version=%d source_id=%u packets=%llu flows=%llu lost=%llu windowfail=%llu reset=%llu dups=%llu",
			buf_tmp,
			source->sourceinfo.version,
			source->sourceinfo.xs.source_id,
			source->npackets,
			source->nflows,
			source->nlost,
			source->nwindowfail,
			source->nreset,
			source->ndup
		);
	}
}

